﻿using Common;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AlgorithmCenter
{
    public class AlgorithmCenter200715
    {
        private char[,] _maze= {

            {'#','S','#','#','#','#','#','#','.','#' },
            {'.','.','.','.','.','.','#','.','.','#' },
            {'.','#','.','#','#','.','#','#','.','#' },
            {'.','#','.','.','.','.','.','.','.','.' },
            {'#','#','.','#','#','.','#','#','#','#' },
            {'.','.','.','.','#','.','.','.','.','#' },
            {'.','#','#','#','#','#','#','#','.','#' },
            {'.','.','.','.','#','.','.','.','.','.' },
            {'.','#','#','#','#','.','#','#','#','.' },
            {'.','.','.','.','#','.','.','.','G','.' },
            {'.','.','.','.','#','.','.','#','.','.' }

        };
        private int _sx=0, _sy=1;
        private int _ex=9, _ey=8;
        private int _maxPath => int.MaxValue;

        private int[] _xMove = {0, 1,0,-1};
        private int[] _yMove = {-1, 0,1,0};


        /// <summary>
        /// 计算迷宫中从开始节点到某个结束节点的最小距离
        /// http://www.zhangxymafx.com/2020/07/15/%E5%AE%BD%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2-----%E8%A7%A3%E5%86%B3%E8%BF%B7%E5%AE%AB%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%E9%97%AE%E9%A2%98/
        /// </summary>
        /// <returns></returns>
        public int CaluateMazeShortestPath()
        {
            int h = _maze.GetLength(0);
            int w = _maze.GetLength(1);

            //存储从开始位置到每个位置的举例
            int[,] path=new int[h,w];
            path.InitToSameValue(int.MaxValue);
            path[_sx, _sy] = 0;

            //用于实现BFS的队列
            Queue<Point> que = new Queue<Point>();

            //先将开始点坐标存入队列
            que.Enqueue(new Point(_sx,_sy));


            while (que.Count > 0)
            {
                var p = que.Dequeue();
                
                //如果发现已经到达目标点，那么不需要在遍历队列中的其他点，说明已经通过最短路径到达了这个点
                if (_maze[p.X, p.Y] == 'G')
                    break;

                //向四个方向移动
                for (int i = 0; i < 4; i++)
                {
                    int dx = p.X + _xMove[i];
                    int dy = p.Y + _yMove[i];

                    //当path[dx,dy]==int.MaxValue时说明该点还没有被遍历到
                    if (dx>=0&&dx<h&&dy>=0&&dy<w&&_maze[dx,dy]!='#'&&path[dx,dy]==int.MaxValue)
                    {
                        path[dx, dy] = path[p.X, p.Y] + 1;
                        que.Enqueue(new Point(dx,dy));
                    }
                }

            }
            return path[_ex,_ey];
        }


        class Point {
            public Point(int x, int y)
            {
                X = x;
                Y = y;
            }
            public int X { get; set; }

            public int Y { get; set; }
        }
    }
}
